# IPv6(不懂)
# 2025/5/23

"""
小蓝最近在学习网络工程相关的知识。他最近学习到，IPv6 地址本质上是 一个 128 位的二进制数，而字符串形式的 IPv6 地址是由被冒号分开的
八段 16 进制数组成的, 例如，下面每行是一个字符串形式的 IPv6 地址:

0000:0000:0000:0000:0000:0000:0000:0000
0000:0001:0000:0000:0000:0001:0000:0000
0000:0001:00ab:0000:0023:0000:0a00:0e00
0000:0000:00ab:0000:000a:0001:0a00:0e00
0000:0000:00ab:0000:0000:0001:0a00:0e00

其中，每一段最长 4 位，且每一段的前导零都可以去掉（如果 4 位都为 0 需要写成 0）。
另外，IPv6 地址还可以将其中相邻的值为 0 的段合并压缩起来，用两个冒 号来表示，不过只能压缩一段。

例如上述地址最短的压缩后的形式分别为:

::
0:1::1:0:0
0:1:ab::23:0:a00:e00
::ab:0:a:1:a00:e00
0:0:ab::1:a00:e00

小蓝想知道, 所有 IPv6 地址的最短压缩形式的长度的和为多少？由于答案 很大（甚至超过了 128 位二进制整数的范围），
请填写答案时填写这个总和除以 109 + 7 的余数。
"""

def sum_shortest_len():
    MOD = 10**9 + 7

    # 非零分组可选的长度和对应的取值个数
    non_zero_len = [1, 2, 3, 4]
    non_zero_ways = [15, 240, 3840, 61440]

    # dp_cur[cur_run][max_run][sum_len] 表示：
    # 已处理若干段后，当前连续零段数 = cur_run，
    # 历史最长连续零段数 = max_run，
    # 已累计字符数 = sum_len 时的方案数
    # 维度大小：cur_run 最多 8，max_run 最多 8，sum_len 最多 32
    dp_cur = [[[0]*33 for _ in range(9)] for __ in range(9)]
    dp_nxt = [[[0]*33 for _ in range(9)] for __ in range(9)]

    # 初始状态：还没处理任何段，cur_run = max_run = sum_len = 0，有 1 种方案
    dp_cur[0][0][0] = 1

    # 逐段处理，共 8 段
    for _ in range(8):
        # 清空下一轮状态
        for i in range(9):
            for j in range(9):
                for k in range(33):
                    dp_nxt[i][j][k] = 0

        # 枚举当前所有状态
        for cur_run in range(9):
            for max_run in range(9):
                for sum_len in range(33):
                    cnt = dp_cur[cur_run][max_run][sum_len]
                    if cnt == 0:
                        continue

                    # 1) 当前段为零分组："0"
                    nr = cur_run + 1
                    nm = max(max_run, nr)
                    ns = sum_len + 1
                    if ns <= 32:
                        dp_nxt[nr][nm][ns] = (dp_nxt[nr][nm][ns] + cnt) % MOD

                    # 2) 当前段为非零分组，长度 1~4，各有 non_zero_ways[i] 种
                    for L, ways in zip(non_zero_len, non_zero_ways):
                        ns2 = sum_len + L
                        if ns2 <= 32:
                            # 连续零段断掉，cur_run 变为 0，max_run 不变
                            dp_nxt[0][max_run][ns2] = (
                                                              dp_nxt[0][max_run][ns2] + cnt * ways
                                                      ) % MOD

        # 切换 dp_cur 和 dp_nxt
        dp_cur, dp_nxt = dp_nxt, dp_cur

    # 处理完 8 段后，统计所有方案的最短表示长度总和
    answer = 0
    for cur_run in range(9):
        for max_run in range(9):
            for sum_len in range(33):
                cnt = dp_cur[cur_run][max_run][sum_len]
                if cnt == 0:
                    continue

                # 未压缩总长度 = sum_len + 7 个冒号
                base_len = sum_len + 7
                # 如果 max_run >= 2，可压缩连串零分组
                # 压缩可减少字符数 = 2*max_run - 3
                reduce = 2 * max_run - 3 if max_run >= 2 else 0
                min_len = base_len - reduce

                answer = (answer + min_len * cnt) % MOD

    return answer


if __name__ == '__main__':
    print(sum_shortest_len())  # 983499503